package org.zxp.algorithm.sort;

import org.junit.Test;

/**
 * @program: algorithm
 * @description: 希尔排序实现
 * 是插入排序的一个变种
 * 将待排序的列表（长度N）分成N/2个序列
 * 在这N/2个序列中，分别做插入排序
 * 排序完成的子序列进行合并
 * 合并完成后 在对合并完成的序列分为 N/2/2个序列
 * 然后再分别对子序列做插入排序，再合并
 * 直到分的序列为1，则最后对整个序列做一次插入排序即可
 * @author: X-Pacific zhang
 * @create: 2019-04-09 10:17
 **/
public class ShellSort {
    @Test
    public void testMname() throws Exception {
        int[] oraArray = {9,2,7,4,8};
        int[] resultArray = shellSort2(oraArray);
        for (int i : resultArray) {
            System.out.println(i);
        }
    }

    public int[] shellSort(int[] orgArray) throws Exception {
        // 9 2 7 4 8    5个元素
        // increment = n/2 = 5/2 = 2;
        // 9 _ 7 _ 8 做插入排序 0 2 4
        // _ 2 _ 4   做插入排序
        // 7 _ 8 _ 9
        // _ 2 _ 4   合并
        // increment = increment/2 = 1;
        // 7 2 8 4 9 做插入排序
        // 2 4 7 8 9
        int n=orgArray.length;
        int gap=n/2;
        while(gap>=1) {
            for (int i = gap; i < orgArray.length; i++) {
                int j = 0;
                int temp = orgArray[i];
                for (j = i - gap; j >= 0 && temp < orgArray[j]; j = j - gap) {
                    orgArray[j + gap] = orgArray[j];
                }
                orgArray[j + gap] = temp;
            }
            printResult(orgArray, orgArray.length);
            gap = gap / 2;
        }
        return orgArray;
    }

//        0 1 2 3 4
//        0    2    4    2->0     4->2 4->0    从2开始比
//           1    3       3->1                         从3开始比
//        1 ->0 2-> 2->0 3->2 3>1 3->0
    public int[] shellSort2(int[] orgArray) throws Exception {
        int gap = orgArray.length/2;
        //2
        //1
        for(; gap >= 1;gap = gap/2){//这层先分组 分为2组
            //2 3 4
            //1 2 3 4
            for (int i = gap;i < orgArray.length;i++) {//每次从下标为gap的开始比，顺序应该是：2-0 3-1 4-2 4-0
                //2 0
                //3
                int current = orgArray[i];//记录2
                int j = i - gap;
                for (; j >= 0 && current < orgArray[j]; j = j - gap) {
                    orgArray[j + gap] = orgArray[j];// 2和0比，如果2比0小就要把0移位
                }
                orgArray[j + gap] = current;//最后再把2插入0的位置
            }
        }
        return orgArray;
    }

    private void printResult(int[] a, int n){
        for(int j=0;j<n;j++){
            System.out.print(" "+a[j]);
        }
        System.out.println();
    }
}
